import re


class Solution:
    def strongPasswordChecker(self, s: str) -> int:
        length, rep_count = len(s), 0
        rep_count += 1 if not re.search(r'[0-9]', s) else 0
        rep_count += 1 if not re.search(r'[a-z]', s) else 0
        rep_count += 1 if not re.search(r'[A-Z]', s) else 0
        if length < 6:
            add_count = 6 - length
            return max(rep_count, add_count)
        elif length <= 20:
            lianxu_count = len(re.findall(r"(.)\1{2}", s))
            return max(lianxu_count, rep_count)
        else:
            del_count = length - 20
            ex_list = re.findall(r"((?P<name1>.)(?P=name1){2,100})", s)
            ex_lianxu_count = -len(ex_list) * 2
            for tuples in ex_list:
                ex_lianxu_count += len(tuples[0])
            if ex_lianxu_count > del_count:
                del_list = [len(i[0]) for i in ex_list]
                del_list.sort()
                while del_count:
                    if del_count >= del_list[0] - 2:
                        del_count -= (del_list.pop(0) - 2)
                    else:
                        for i in range(len(del_list)):
                            for j in range(1, del_count + 1):
                                if del_list[i] // 3 > (del_list[i] - j) // 3:
                                    del_list[i] -= j
                                    del_count -= j
                                    break
                        break
                res = 0
                for i in del_list:
                    res += (i // 3)
                return length - 20 + max(res, rep_count)
            else:
                return del_count + rep_count


a = Solution()
print(a.strongPasswordChecker(""))  # 6
print(a.strongPasswordChecker("*" * 21))  # 7
print(a.strongPasswordChecker("*" * 20))  # 6
print(a.strongPasswordChecker("*" * 10 + "a" + "*" * 10))  # 7
print(a.strongPasswordChecker("aaaabbaaabbaaa123456A"))  # 3
print(a.strongPasswordChecker("AAAAAABBBBBB123456789a"))  # 4
print(a.strongPasswordChecker("aaaaaaaAAAAAA6666bbbbaaaaaaABBC"))  # 13
